package main

import (
	"fmt"
	"math"
	"runtime"
)

type Wythoff_Item struct {
	a int
	b int
}

const ARR_SIZE = 100

var (
	abc    Wythoff_Item
	wy_map = make(map[int]int) // 双向map
)

//		a =[k（1+√5）/2]，b= a + k
// 给定威佐夫博奕奇异局势的k，计算数字a
func calc_wythoff_ktoa(k int) int {
	f1 := math.Sqrt(5)
	f2 := float64(k) * (f1 + 1) / 2
	f3 := math.Floor(f2)
	return int(f3)
}

func calc_wythoff_pair(k int) Wythoff_Item {

	var item Wythoff_Item
	item.a = calc_wythoff_ktoa(k)
	item.b = item.a + k
	return item
}

// 给定威佐夫博奕奇异局势的一个数字a，计算另一个数字b
func calc_wythoff_atob(a int) int {
	// 猜测k
	k1 := int(float64(a) / 1.618)
	k2 := int(float64(a+1) / 1.618)
	// fmt.Printf("[%s] a=%d, k's range[%d, %d]\n", printMyName(), a, k1, k2)

	for k := k1; k <= k2; k++ {
		ta := calc_wythoff_ktoa(k)
		// fmt.Printf("[%s] a=%d, k=%d, ta=%d\n", printMyName(), a, k, ta)
		if ta == a {
			return ta + k
		}
	}
	return -1
}

// 给定威佐夫博奕奇异局势的一个数字b，计算另一个数字a
func calc_wythoff_btoa(b int) int {
	// 猜测k
	k1 := int(float64(b) / 2.618)
	k2 := int(float64(b+1) / 2.618)
	// fmt.Printf("[%s] b=%d, k's range[%d, %d]\n", printMyName(), b, k1, k2)

	for k := k1; k <= k2; k++ {
		tb := calc_wythoff_ktoa(k) + k
		// fmt.Printf("[%s] b=%d, k=%d, tb=%d\n", printMyName(), b, k, tb)
		if tb == b {
			return tb - k
		}
	}
	return -1
}

// 给定一个局势，计算比他小的奇异局势
func calc_next_pair(item *Wythoff_Item) bool {

	if item.a == item.b {
		item.a = 0
		item.b = 0
		return true
	}
	// 使用map方式查找
	//	return calc_next_pair_bymap(item)

	// 使用计算k的方式
	if true == calc_next_pair_ex(item) {
		return true
	}

	// 翻个面在找一次
	tmp := Wythoff_Item{a: item.b, b: item.a}
	if true == calc_next_pair_ex(&tmp) {
		item.a, item.b = tmp.b, tmp.a
		return true
	}

	// 只能在两堆里同时取相同个数了
	if item.a < item.b {
		*item = calc_wythoff_pair(item.b - item.a)
	} else {
		tmp := calc_wythoff_pair(item.a - item.b)
		item.a, item.b = tmp.b, tmp.a
	}
	return true
}

func calc_next_pair_ex(item *Wythoff_Item) bool {
	a := calc_wythoff_btoa(item.b)
	b := calc_wythoff_atob(item.a)

	// fmt.Printf("a=%d, b=%d, a1=%d， b1=%d\n", item.a, item.b, a, b)

	if item.b == b || item.a == a {
		fmt.Printf("当前就是奇异局势(%d, %d)", item.a, item.b)
		item.a -= 1
		return true
	}

	if b < item.b && b >= 0 {
		item.b = b
		return true
	} else if a < item.a && a >= 0 {
		item.a = a
		return true
	}
	return false
}

// 给定一个局势，计算比他小的奇异局势
func calc_next_pair_bymap(item *Wythoff_Item) bool {
	b, ok := wy_map[item.a]
	fmt.Printf("find: %d, result: %d %t!\n", item.a, b, ok)
	if ok && b <= item.b {
		item.b = b
		return true
	}

	a, ok := wy_map[item.b]
	fmt.Printf("find: %d, result: %d %t!\n", item.b, a, ok)
	if ok && a <= item.a {
		item.a = a
		return true
	}

	return false
}

func printMyName() string {
	// pc, file, line, ok := runtime.Caller(1)
	pc, _, _, _ := runtime.Caller(1)
	return runtime.FuncForPC(pc).Name()
}

func lost(item *Wythoff_Item) bool {
	if item.a == 0 && item.b == 0 {
		return true
	}
	return false
}

func check_user_do(s1 *Wythoff_Item, s2 *Wythoff_Item) bool {
	if s2.a > s1.a || s2.b > s1.b || (s2.a == s1.a && s2.b == s1.b) {
		return false
	}
	if s2.a < 0 || s2.b < 0 {
		return false
	}
	a := s2.a - s1.a
	b := s2.b - s1.b

	if a == 0 || b == 0 || a == b {
		return true
	} else {
		return false
	}
}
func main() {
	main1()
	return

	func(size int) {
		for i := 0; i < size; i++ {
			a := calc_wythoff_ktoa(i)
			b := a + i
			wy_map[a] = b
			wy_map[b] = a
		}
	}(ARR_SIZE)
	// for key := range wy_map {
	// 	fmt.Printf("%d, %d\n", key, wy_map[key])
	// }

	var item, input Wythoff_Item
	fmt.Printf("威佐夫博弈: \n")
	fmt.Printf("\t有两堆各若干个物品，两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品，\n")
	fmt.Printf("\t规定每次至少取一个，多者不限，最后取光者得胜。\n\n")
	fmt.Printf("输入初始数量(,)：")
	fmt.Scanf("%d,%d\n", &item.a, &item.b)

	for {
		if true == lost(&item) {
			fmt.Print("your win!!\n")
			break
		}

		tmp1 := fmt.Sprintf("\ncomputer: (%d,%d)", item.a, item.b)
		calc_next_pair(&item)
		tmp1 += fmt.Sprintf(" -> (%d,%d), ", item.a, item.b)

		if true == lost(&item) {
			tmp1 += "your lost!!\n"
			fmt.Print(tmp1)
			break
		}
		tmp1 += "and you input:"

		// 检查输入
		for {
			fmt.Print(tmp1)
			fmt.Scanf("%d,%d\n", &input.a, &input.b)
			if true == check_user_do(&item, &input) {
				break
			}
			fmt.Printf("输入错误，请重新输入。")
		}

		item = input

	}

}

/*
威佐夫博奕Wythoff's game
条件：
威佐夫博弈（Wythoff's game）：有两堆各若干个物品，两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
正解：
面对奇异局势先手必输。
如何判断是不是奇异局势：给你（a，b）  a<b
k=b-a   如果 a =[k（1+√5）/2]，b= a + k  （方括号表示取整)   就是奇异局势
解释：
我们用（a[k]，b[k]）（a[k] ≤ b[k] ,k=0，1，2，...,n)（表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，如果甲面对（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）都可以推出甲必输。这一串数有什么规律呢
（ai,bi） ai是前面未出现过的最小整数。bi=ai+k;  k呢是这一串数的序号   第一个是0 然后是1 2 3.。。
同时k也是这几对数每对数（a，b）的差值
这是我们找到的规律  是否就是我们要找的奇异局势也就是必输局面呢
 我们证明一下
证明之前  我们先观察我们发现的规律
很容易发现它有一个性质
任何自然数都包含在一个且仅有一个奇异局势中。
ai是前面未出现过的最小整数。bi=ai+k;由这两个规律， 从数学上可以证明此性质。
然后再看满足我们说的规律的数 是否满足必败态的性质
满足性质1、非必败态一定可以移动到必败态；
面对（a，b）一对数，只有 相等和不相等两种情况。不管相等还是不相等，根据刚才提到的性质，都必然有一个数属于一个奇异局势，而我们只要对另一个数进行减法操作就可以使它变为奇异局势。（主要是因为性质：.每个数，必然存在它对应的奇异局势。）我们很容易变到奇异局势。
满足性质2、在必败态做的所有操作的结果都是非必败态。
根据性质1，若只改变奇异局势（a[k]，b[k]）的某一个分量，那么另一个分量不可能出现在其他奇异局势中，所以必然是非奇异局势。如果使（a[i]，b[i]）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。（每个奇异局势的差是唯一的）

所以符合我们规律的就是我们要找的必败局面 奇异局势
那么我们只要判断出符合我们找到的规律就行
bi=ai+k;   k是（ai，bi）的差值  但是ai不好找
我们进一步发现规律  ai=[k*1.618]方括号代表取整。（0.618是黄金分割数，但是我们写代码不能写0.618，因为后边还有小数需要精确，所以我们写   (1+sqrt(5) )/2
1.618=（1+sqrt（5））/2
所以  结论是如果a =[k（1+√5）/2]，b= a + k  （方括号表示取整)   就是奇异局势

*/
